package dynamicprogramming;

/**
 * @Author: LDeng
 * @Date: 2021-04-21 16:14
 */
public class CoinChange {

    public static void main(String[] args) {
        System.out.println(coins5(41, new int[]{5, 20, 25}));
        //System.out.print(coins3(41));
        //System.out.println(coins1(41));
        //System.out.println(coins2(41));
    }

    static int coins5(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i < face) continue;
                if (dp[i - face] < 0 || dp[i - face] >= min) continue;
                min = dp[i - face];
            }
            if (min == Integer.MAX_VALUE) {
                dp[i] = -1;
            } else {
                dp[i] = min + 1;
            }

        }
        return dp[n];
    }

    //凑够n分钱需要的最少金币数(递推-自底向上)
    static int coins3(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        int[] faces = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // dp[i]=min{dp[i-25],dp[i-20],dp[i-5],dp[i-1]}+1;
            int min = Integer.MAX_VALUE;
            if (i >= 1 && dp[i - 1] < min) {
                min = dp[i - 1];
                faces[i] = 1;//凑够i分钱时最后选择的那枚硬币的面值
            }
            if (i >= 5 && dp[i - 5] < min) {
                min = Math.min(dp[i - 5], min);
                faces[i] = 5;
            }
            if (i >= 20 && dp[i - 20] < min) {
                min = Math.min(dp[i - 20], min);
                faces[i] = 20;
            }
            if (i >= 25 && dp[i - 25] < min) {
                min = Math.min(dp[i - 25], min);
                faces[i] = 25;
            }
            dp[i] = min + 1;
            print(faces, i);
        }
        //print(faces, n);
        return dp[n];
    }

    static void print(int[] faces, int n) {
        System.out.print("[" + n + "]=");
        while (n > 0) {
            System.out.print(faces[n] + " ");
            n = n - faces[n];//凑够n数额的钱需要的最后一枚硬币的面值
        }
        System.out.println();
    }


    //凑够n分钱需要的最少金币数(记忆化搜索)
    static int coins1(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //dp[1] = dp[5] = dp[20] = dp[25] = 1; 防止数组越界， 改成下面代码 ，做判断
        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (n < face) break;
            dp[face] = 1;
        }
        return coins1(n, dp);
    }

    static int coins1(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            int min1 = Math.min(coins1(n - 25, dp), coins1(n - 20, dp));
            int min2 = Math.min(coins1(n - 5, dp), coins1(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
            for (int i = 0; i < dp.length; i++) {
                System.out.println("dp" + "[" + i + "]=>" + dp[i]);
            }
            System.out.println("-------------");
        }
        return dp[n];
    }


    //凑够n分钱最少需要的金币数(暴力递归， 很多重叠子问题)
    static int coins2(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;//递归基
        int min1 = Math.min(coins2(n - 25), coins2(n - 20));
        int min2 = Math.min(coins2(n - 5), coins2(n - 1));
        int min = Math.min(min2, min1);
        return min + 1;
    }


}
